import java.util.LinkedList;

public class Solution {

    /**
     * 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
     */
    public static int longestValidParentheses(String s) {
        char[] chars = s.toCharArray();
        boolean[] marks = new boolean[chars.length];
        LinkedList<Integer> stackIdx = new LinkedList<>();

        for (int i = 0; i < chars.length; i++) {
            char cur = chars[i];
            if (cur == '(') {
                stackIdx.addLast(i);
            } else if (cur == ')') {
                if (stackIdx.isEmpty()) {
                    marks[i] = false;
                } else {
                    marks[i] = true;
                    marks[stackIdx.removeLast()] = true;
                }
            }
        }

        int max = 0;
        int count = 0;
        for (boolean m : marks) {
            if (m) {
                count++;
            } else {
                if (count != 0) {
                    max = Math.max(max, count);
                    count = 0;
                }
            }
        }

        if (count != 0) {
            max = Math.max(max, count);
        }

        return max;
    }

    public static void main(String[] args) {
        longestValidParentheses("(()()))(()");
        longestValidParentheses("(()");
        longestValidParentheses(")()())");

    }


}